//
// Description: 31. 下一个排列
// Created by Loading on 2022/3/20.
//

#include <bits/stdc++.h>

using namespace std;

void nextPermutation(vector<int> &nums) {
    int i = (int) nums.size() - 2;
    // 从后向前寻找第一个未单调不减的位置 （较小数尽量靠右）
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = (int) nums.size() - 1;
        // 从后向前寻找第一个大于 i 位置的数 （较大数尽量小）
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        // 两个位置元素交换
        swap(nums[i], nums[j]);
    }
    // 最后反转 i 位置之后的所有元素，如果数组原本就是单调不增，则整体反转
    reverse(nums.begin() + i + 1, nums.end());
}

int main() {
    vector<int> nums{3, 2, 1};
    nextPermutation(nums);
    for (auto x : nums) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}